package BinaryTree;//给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节
//点为空。 
//
// 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。 
//
// 示例 1: 
//
// 
//输入: 
//
//           1
//         /   \
//        3     2
//       / \     \  
//      5   3     9 
//
//输出: 4
//解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
// 
//
// 示例 2: 
//
// 
//输入: 
//
//          1
//         /  
//        3    
//       / \       
//      5   3     
//
//输出: 2
//解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
// 
//
// 示例 3: 
//
// 
//输入: 
//
//          1
//         / \
//        3   2 
//       /        
//      5      
//
//输出: 2
//解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
// 
//
// 示例 4: 
//
// 
//输入: 
//
//          1
//         / \
//        3   2
//       /     \  
//      5       9 
//     /         \
//    6           7
//输出: 8
//解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
// 
//
// 注意: 答案在32位有符号整数的表示范围内。 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 265 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class widthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {

        /**
         * 模拟了二叉树 层次遍历下的顺序，即当父节点编号为x时，它的左孩子编号为x*2，有孩子为x*2+1
         * 在遍历每一层时，对该层的节点的孩子节点的val，重写为在层次遍历下的位置
         * 利用双向队列可以在每一层可以取最左和最右节点，他们的编号差即宽度
         * */
        int res = 0;
        if(root==null){
            return res;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            int left = queue.peekFirst().val;  //当前层最左
            int right = queue.peekLast().val;  //当前层最右
            res = Math.max(res,right-left+1);
            while(len>0){
                TreeNode curr = queue.poll();
                if (curr.left!=null){
                    curr.left.val = curr.val * 2;
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    curr.right.val = curr.val * 2 + 1;
                    queue.offer(curr.right);
                }
                len--;
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
